package leetcode.math;

import java.util.Arrays;

public class CountPrimes {
    class Solution1 {
        public int countPrimes(int n) {
            if (n <= 2) {
                return 0;
            }
            boolean[] isPrime = new boolean[n];
            Arrays.fill(isPrime, true);
            int count = n - 2;
            for (int i = 2; i < n; i++) {
                if (isPrime[i]) {
                    for (int j = i * 2; j < n; j += i) {
                        if (isPrime[j]) {
                            isPrime[j] = false;
                            count--;
                        }
                    }
                }
            }
            return count;
        }
    }


    class Solution2 {
        public int countPrimes(int n) {
            if (n <= 2) {
                return 0;
            }
            boolean[] isPrime = new boolean[n];
            Arrays.fill(isPrime, true);
            int i = 3;
            int sqrtn = (int) Math.sqrt(n);
            int count = n / 2;
            while (i <= sqrtn) {
                for (int j = i * i; j < n; j += 2 * i) {
                    if (isPrime[j]) {
                        --count;
                        isPrime[j] = false;
                    }
                }
                do {
                    i += 2;
                } while (i <= sqrtn && !isPrime[i]);
            }
            return count;
        }
    }
}
